package algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessBoard {

//  列
  private static int X;
//  行
  private static int Y;
//  创建一个数组，标记棋盘的各个位置是否被访问过
  private static boolean visited[];
//  使用一个属性，标记是否棋盘的所有位置都被访问
  private static boolean finished; //如果为true,表示成功

  private static void traverl(int[][]chessBoard,int row,int column,int step) {

    chessBoard[row][column] = step;
//    标记该位置走过
    visited[row * X + column] = true;
//    获取当前位置可以走的下一个位置的集合
    ArrayList<Point> next = next(new Point(column, row));
//    对next进行排序,排序的规则就是对next的所有的Point对象的下一步的位置的数目，进行非递减排序
    sort(next);
    while (!next.isEmpty()) {//取出下一个可以走的位置
      Point p = next.remove(0);
      if (!visited[p.y * X + p.x]) {//表示该位置没有被访问过
        traverl(chessBoard, p.y, p.x, step + 1);
      }
    }
//    判断马儿是否完成了任务,使用step和应该走的步数比较,
//    如果没有达到数量，则表示没有完成任务，将整个棋盘置空
//    step < X * Y  成立的两种情况：处于回溯状态；没走完
    if (step < X * Y & !finished) {
      chessBoard[row][column] = 0;
      visited[row * X + column] = false;
    }else {
      finished = true;
    }
  }

//  根据当前这个一步的所有的下一步的选择位嚣,进行非递减排序
  private static void sort(ArrayList<Point> ps){
    ps.sort(new Comparator<Point>() {
      @Override
      public int compare(Point o1, Point o2) {
//        获取到o1的下一步的所有位置个数
        int count1 = next(o1).size();
//        获取到o2的下一步的所有位置个数
        int count2 = next(o2).size();
        if (count1 < count2){
          return -1;
        }else if (count1 == count2){
          return 0;
        }else {
          return 1;
        }
      }
    });
  }

  public static void main(String[] args) {

    System.out.println("骑士周游算法开始运行：");

    X = 8;
    Y = 8;
    visited = new boolean[X * Y];
    int row = 1;//马儿初始行的位置，第一行
    int column = 1;//马儿初始列的位置，第一列
//    初始化棋盘
    int[][]chess = new int[X][Y];
//    开始时间
    long start = System.currentTimeMillis();
    traverl(chess,row - 1,column - 1,1);
//    结束时间
    long end = System.currentTimeMillis();
    System.out.println("共耗时：" + (end - start) + "毫秒");
//    遍历棋盘
    for (int[] rows : chess) {
      for (int step : rows) {
        System.out.print(step + "\t" );
      }
      System.out.println();
    }



  }

//  功能：根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList)，最多有8个位置
  public static ArrayList<Point> next(Point curPoint){
    /*
    0 6 0 7 0
    5 0 0 0 8
    0 0 x 0 0
    4 0 0 0 1
    0 3 0 2 0

     */
//    创建一个ArrayList
    ArrayList<Point> ps = new ArrayList<>();
//    创建一个point
    Point p1 = new Point();
//    判断马儿是否可以走5这个位置
    if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0){
      ps.add(new Point(p1));
    }
//    判断马儿是否可以走6这个位置
    if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0){
      ps.add(new Point(p1));
    }
//    判断马儿是否可以走7这个位置
    if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0){
      ps.add(new Point(p1));
    }
//    判断马儿是否可以走8这个位置
    if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0){
      ps.add(new Point(p1));
    }
//    判断马儿是否可以走1这个位置
    if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y){
      ps.add(new Point(p1));
    }
//    判断马儿是否可以走2这个位置
    if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y){
      ps.add(new Point(p1));
    }
//    判断马儿是否可以走3这个位置
    if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y){
      ps.add(new Point(p1));
    }
//    判断马儿是否可以走4这个位置
    if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y){
      ps.add(new Point(p1));
    }
    return ps;
  }

}


